import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:字符串的排列
 * User: wangxin
 * Date: 2024-12-25
 * Time: 22:04
 */
public class Test {
    public void recursion(ArrayList<String> res,char[] ch,boolean[] vis,StringBuffer temp){
        if(ch.length == temp.length()){
            res.add(new String(temp));
            return;
        }
        for(int i = 0; i < ch.length;i++){
            if(vis[i]){
                continue;
            }
            if(i > 0&&ch[i-1] == ch[i]&&!vis[i-1]){
                continue;
            }
            vis[i] = true;
            temp.append(ch[i]);
            recursion(res,ch,vis,temp);
            vis[i] = false;
            temp.deleteCharAt(temp.length()-1);
        }
    }
    public ArrayList<String> Permutation (String str) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        if(str == null||str.length() == 0){
            return null;
        }
        char[] ch = str.toCharArray();
        Arrays.sort(ch);
        boolean[] vis = new boolean[ch.length];
        Arrays.fill(vis,false);
        StringBuffer temp = new StringBuffer();
        recursion(res,ch,vis,temp);

        return res;
    }
}
